Date: Wed, 08 Jan 1997 20:43:56 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CSE 322 
Assignment 4 
Due Friday, January 26, 1996</TITLE>
</HEAD>
<BODY>
<meta name="description" value="CSE 322 
Assignment 4 
Due Friday, January 26, 1996">
<meta name="keywords" value="hw4">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>CSE 322 
Assignment 4 
Due Friday, January 26, 1996</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
<OL><LI> 
Number 36 on page 69.  Better yet construct the derivation tree for
<IMG  ALIGN=MIDDLE ALT="" SRC="img1.gif">.
<LI>
Consider the grammar: <IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif">.  
<OL><LI>
By example show that this grammar is ambiguous.
<LI>
Design an unambiguous grammar which generates the same language
as this grammar.  Explain why your grammar
is unambiguous.
</OL>
<LI> Use the construction given in class for producing a regular grammar
from a regular expression to construct a regular grammar which generates
the language defined by the regular expression <IMG  ALIGN=MIDDLE ALT="" SRC="img3.gif">.
<LI>
Let <b>L</b> be the subset of <IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif"> where the <b>a</b>'s and <b>b</b>'s are matched
as parentheses.  The grammar <b>G</b> with
productions  <IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif">.  
generates this language.  Prove by induction on the length of 
a derivation that if <IMG  ALIGN=BOTTOM ALT="" SRC="img6.gif"> and <IMG  ALIGN=MIDDLE ALT="" SRC="img7.gif">
then <b>x</b> satisfies the two
properties (i) every prefix of <b>x</b> has at least as many <b>a</b>'s as <b>b</b>'s
and (ii) <b>x</b> has an equal number of <b>a</b>'s as <b>b</b>'s.
<P>
Note that there is only one derivation of length 1, namely, <IMG  ALIGN=BOTTOM ALT="" SRC="img8.gif">.
For the inductive step, if <IMG  ALIGN=BOTTOM ALT="" SRC="img9.gif"> then there are two
possibilities <IMG  ALIGN=BOTTOM ALT="" SRC="img10.gif"> or
<IMG  ALIGN=BOTTOM ALT="" SRC="img11.gif">.  Your job is to carefully complete
the induction proof using these ideas.
</OL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Mon Jan 22 10:11:12 PST 1996</I>
</ADDRESS>
</BODY>
